/**
 * @file
 * Given many-to-many mapping between two sets produce all one-to-one mappings. 
 * Consider two sets, A = {1, 2, 3} and B = {4, 5, 6}. 
 * Futhermore consider the following many-to-one mapping between the 
 * two sets M = {{1, 4}, {1, 5}, {1, 6}, {2, 5}, {2, 6}, {3, 5}, {3, 6}} 
 * It is possible to have two one-to-one mappings between A and B,
 * M1 = {{1, 6}, {2, 5}, {3, 4}} and  M2 =  {{1, 6}, {2, 4}, {3, 5}}. 
 * Given A, B and M, this module produces M1 and M2. 
 */

#ifndef PAIRINGS_H
#define PAIRINGS_H

#include <map>
#include <set>
#include <vector>
#include <list>
#include <stack>

/**
 * Given many-to-many mapping between two sets produce all one-to-one mappings.
 */
template<class T>
class Pairings
{
public:
  Pairings() {first = true;} 
  void add_pair(T *from, T *to);
  bool get_next_map(std::map<T*, T*> *result);
private:
  // Input data storage
  std::set<T*> from_set;
  std::set<T*> to_set;
  std::map<T*, std::set<T*> > combined_map;

  // Stacks to store the remaning 'from' set, the remaning 'to' set 
  // and the partial mappings
  std::stack<std::set<T*> > from_stack;
  std::stack<std::set<T*> > to_stack;
  std::stack<std::map<T*, T*> > map_stack;
  bool first;
};

/**
 * Adds a pair to the map.
 * @param[in] from The member from which to map. 
 * @param[in] to The member to which to map .
 */
template<class T>
void Pairings<T>::add_pair( T *from, 
                            T *to)
{
  // Insert given pair into the map
  (combined_map[from]).insert(to);

  // Insert each of the elements in the 
  // pair in to their respective sets
  from_set.insert(from);
  to_set.insert(to);
}

/**
 * Gets next one-to-one mapping. 
 * @param[out] result Result location to write to.
 * @return @c false if all maps completed, @c true otherwise.
 */
template<class T>
bool Pairings<T>::get_next_map(std::map<T*, T*> *result)
{
  // Perform initialization on first invocation
  if(first)
    {
      first = false;

      from_stack.push(from_set);
      to_stack.push(to_set);
      
      std::map<T*, T*> map_copy;
      map_stack.push(map_copy);
    }

  // If stack is empty, all maps have been processed
  while(! from_stack.empty())
    {
      // Pop the remaning from set, to set and 
      // the partial mapping from the stack
      std::set<T*> given_from_set = from_stack.top(); from_stack.pop();
      std::set<T*> given_to_set = to_stack.top(); to_stack.pop();
      std::map<T*, T*> given_map = map_stack.top(); map_stack.pop();
      
      // Check if the partial mapping is completed
      if(given_from_set.empty())
        {  
          // Copy the result and return true
          *result = given_map;
          return true;
        }
      else
        {
          // Iterate through the remaning members of the 'from' set 
          for(typename std::set<T*>::iterator i = given_from_set.begin(); 
              i != given_from_set.end(); 
              i++)
            {
              // Create a new copy of the 'from' set
              std::set<T*> from_set_copy = given_from_set;

              // Erase the current member from the copy
              from_set_copy.erase(*i);

              // Get the set of matching elements from the 'to' set 
              // that match the current 'from' member
              std::set<T*> matches = combined_map[*i];
              
              // Get first element of this set of matching elements
              typename std::set<T*>::iterator j = given_to_set.begin();
              
              // Check if this element is present in the remaning 'to' set
              if(matches.find(*j) != matches.end())
                {
                  // Create a new copy of the 'to' set
                  std::set<T*> to_set_copy = given_to_set;

                  // Erase the current member from the copy
                  to_set_copy.erase(*j);
                  
                  // Create a new copy of the partial map and add the new pair
                  std::map<T*, T*> map_copy = given_map;
                  map_copy[*i] = *j;

                  // Push the new from set, to set and the partial 
                  // mapping from the stack                 
                  from_stack.push(from_set_copy);
                  to_stack.push(to_set_copy);
                  map_stack.push(map_copy);
                }
            }
        }              
    }
  // If stack is empty, all maps have been processed
  return false;
}

#endif // PAIRINGS_H

